package org.example.myleet.p497;

public class Solution {

    private final int len;
    private final double[] preSum;
    private final int[][] rectangles;
    private final int[] areas;

    /**
     * 思路方法：每个矩形都有对应数量的点，每个矩形被选中的概率对应矩形的点数/总的点数，
     * 利用前缀和可以确定矩形的概率在总概率中的位置，随机投出的一个小数，通过遍历前缀和就可以确定应该选哪一个矩形
     * 然后利用投出的随机小数在当前矩形中的概率位置计算应该选第几点
     * @param rects 题目给定的举行区域
     */
    public Solution(int[][] rects) {
        rectangles = rects;
        len = rectangles.length;
        preSum = new double[rects.length + 1];
        areas = new int[rects.length];
        //计算每个矩形的点数和总点数
        int totalArea = 0;
        for (int i = 0; i < len; ++i) {
            int[] rect = rectangles[i];
            int w = rect[2] - rect[0] + 1;
            int h = rect[3] - rect[1] + 1;
            areas[i] = w * h;
            totalArea += areas[i];
        }
        //计算每个矩形的点数对应的占比的前缀和，[0, p1, p2...pn, 1.0]，其中p1～pn都是0到1之间的小数
        double sum = 0.0;
        for (int i = 0; i < len; ++i) {
            double distribution = (double) areas[i] / (double) totalArea;
            sum += distribution;
            preSum[i + 1] = sum;
        }
    }

    public int[] pick() {
        //先随机砸出一个小数
        double rand = Math.random();
        //遍历前缀和以确定砸出的结果选中哪一个矩形
        int i = 0;
        for (; i < len; ++i) {
            if (preSum[i] <= rand && rand < preSum[i + 1]) {
                break;
            }
        }
        int[] rect = rectangles[i];
        //接下来计算percentage，用于计算矩形中应该选第seq点，
        //当前砸出的小数在矩形中所有点所占的大小为rand - preSum[i]，而矩形i的总的概率是preSum[i + 1] - preSum[i]
        //比重percentage = 砸出的小数在矩形中所有点所占的大小 / 矩形i的总的概率
        double percentage = (rand - preSum[i]) / (preSum[i + 1] - preSum[i]);
        //seq是矩形中的第几点，从左下角开始算，用矩形i的点数 * percentage
        int seq = (int) (areas[i] * percentage);
        //计算矩形一行有多少个点，结果所选的点就是第(seq / w)行，第(seq % w)列
        int w = rect[2] - rect[0] + 1;
        return new int[]{rect[0] + seq % w, rect[1] + seq / w};
    }
}
